package com.likou;

import java.util.Deque;
import java.util.LinkedList;

public class q19 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode ans = new ListNode(0, head);
        Deque<ListNode> deque = new LinkedList<>();

        ListNode p = ans;
        while (p != null) {
            deque.push(p);
            p = p.next;
        }

        for (int i = 0; i < n; i++) {
            deque.pop();
        }

        p = deque.peek();
        p.next = p.next.next;

        return ans.next;
    }


//    public ListNode removeNthFromEnd(ListNode head, int n) {
//        if (head.next == null) {
//            return null;
//        }
//        ListNode p = head;
//        int len = 0;
//        while (p != null) {
//            len++;
//            p = p.next;
//        }
//
//        p = head;
//        int mark = 0;
//        while (p != null) {
//            mark++;
//            if (len - n == 0) {
//                head = head.next;
//                return head;
//            }
//            if (mark == (len - n)) {
//                ListNode temp = p.next;
//                p.next = p.next.next;
//                temp.next = null;
//            }
//            p = p.next;
//        }
//
//        return head;
//    }

}
